/*
 * Copyright (C) 2000-2005 Philips Electronics N.V.
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or 
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; see the file gnu_license.txt.  If not, write to
 * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
 * 
 */
#include <cfront.h>
#include "cfrontPrint.h"
#include "type.h"
#include "spectype.h"
#include "typing.h"
#include "expressions.h"
#include "eval.h"
#include "errors.h"
#include "fe_flags.h"

/* 0 */
static struct s_void_cfront_TraverseTable clear_types;
/* 1 */
static struct s_cfront_TraverseTable      give_base_types;
/* 2 */
static struct s_void_cfront_TraverseTable type_declarators;
/* 3 */
static struct s_void_cfront_TraverseTable type_old_parameters;
static struct s_void_cfront_TraverseTable type_holders;
/* 4 */
static struct s_void_cfront_TraverseTable finish_types;
/* 5 */
static struct s_void_cfront_TraverseTable BU_typing;
/* 6 */
static struct s_void_cfront_TraverseTable check_typing;

static void init_traversals(void);
static Type specifier_type (declaration_specifier spec, Type u);
static List_expression type_initializer (Type t, List_expression es);


/* ----------------------------------------------------------------------------
 * Type checks
 */
static Bool
chk_pointer_type (Type t, expression me)
{
  if (is_pointer_type(t)) return TRUE;
  pointer_type_required (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_scalar_type (Type t, expression me)
{
  if (is_scalar_type(t)) return TRUE;
  scalar_type_required (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_integral_type (Type t, expression me)
{
  if (is_integral_type(t)) return TRUE;
  integral_type_required (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_arithmetic_type (Type t, expression me)
{
  if (is_arithmetic_type(t)) return TRUE;
  arithmetic_type_required (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_ptr_to_function_type (Type t, expression me)
{
  if (is_pointer_type(t)) {
    t = dereference_type (t);
    if (is_function_type(t)) return TRUE;
  }
  function_type_required(me, Text_expression (me));
  return FALSE;
}

static Bool
chk_complete_type (Type t, expression me)
{
  if (!is_incomplete_type(t)) return TRUE;
  incomplete_type_forbidden (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_struct_type (Type t, expression me)
{
  if (is_structured_type(t)) return TRUE;
  member_of_non_struct (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_non_bitfield (Type t, expression me)
{
  if (!is_bitfield_type(t)) return TRUE;
  bitfield_forbidden (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_non_register (expression me)
{
  if (!expr_in_register(me)) return TRUE;
  address_of_register (me);
  return FALSE;
}

static Bool
chk_non_function (Type t, expression me)
{
  if (!is_function_type(t)) return TRUE;
  function_type_forbidden (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_non_array_type (Type t, expression me)
{
  if (!is_array_type(t)) return TRUE;
  array_type_forbidden (me, Text_expression (me));
  return FALSE;
}

static Bool
chk_qualifiers (Type l, Type r, expression me)
{
  if (is_void_pointer_type(l)) return TRUE;
  if (is_void_pointer_type(r)) return TRUE;
  if (has_qualifier_subset (r, l)) return TRUE;
  insufficiently_qualified (me);
  return FALSE;
}

/* ----------------------------------------------------------------------------
 * Add the qualifiers QUAL to type T
 */
static Type
add_qualifier (Type t, type_qualifier qual)
{
  switch (type_qualifier_tag (qual)) {
  case Const_kind: case Const1_kind: case Const2_kind:
    return make_const (t);
  case Volatile_kind: case Volatile1_kind: case Volatile2_kind:
    return make_volatile (t);
  case Restrict_kind: case Restrict1_kind: case Restrict2_kind:
    if (!have_restrict) no_restrict (qual);
    return make_restrict (t);
  case GnuAttribute_kind:
    return type_add_attributes (t, GnuAttribute_attr (qual));
  }
  abort();
}

/* ----------------------------------------------------------------------------
 * Convert E to type TO
 */
static Type
type_convert_expression (expression e, Type to)
{
  expression_req_type (e) = to;
  return to;
}

/* ----------------------------------------------------------------------------
 * Integral Promotion (ANSI-C 3.2.1.1)
 * Pre: A has an integral type
 */
static Type
integral_promotion(expression a)
{
  Type r = int_type;
  Type at = expression_type (a);

  if (is_long_long_type (at) ||
      is_long_int_type (at) ||
      is_enum_type (at)) {
    return at;
  }
  if (is_unsigned_type (at)) r = make_unsigned (r);
  return type_convert_expression (a, r);
}

/* ----------------------------------------------------------------------------
 * Default argument promotions (3.3.2.2)
 */
static Type
default_argument_promotion(expression a)
{
  Type at = expression_type (a);

  if (is_floating_type (at)) {
    if (expanded_base_type (at) != float_type) return at;
    return type_convert_expression (a, double_type);
  }
/* In C89:3.3.2.2 and C99:6.5.2.2: "No other conversions are performed implicitly."
   I think this answers the following questions with "No."
     warning TODO: are (function)-pointers really promoted to int
     warning TODO: what about structs??
*/
  if (is_integral_type(at)) {
    return integral_promotion (a);
  }
  return at;
}

/* ----------------------------------------------------------------------------
 * Usual Arithmetic Conversions (ANSI-C 3.2.1.5)
 */
static Type
arithmetic_conversion(expression a, expression b)
{
  Type at = expression_type (a);
  Type bt = expression_type (b);

  if (is_long_double_type (at)) return type_convert_expression (b, at);
  if (is_long_double_type (bt)) return type_convert_expression (a, bt);
  if (is_double_type (at)) return type_convert_expression (b, at);
  if (is_double_type (bt)) return type_convert_expression (a, bt);
  if (is_float_type (at)) return type_convert_expression (b, at);
  if (is_float_type (bt)) return type_convert_expression (a, bt);

  at = integral_promotion (a);
  bt = integral_promotion (b);

  if (is_unsigned_type(at) && is_long_int_type(at)) {
    return type_convert_expression (b, at);
  }
  if (is_unsigned_type(bt) && is_long_int_type(bt)) {
    return type_convert_expression (a, bt);
  }

  if (is_long_int_type (at) && is_unsigned_type (bt)) {
    if (unsigned_int_fits_long) return type_convert_expression (b, at);
    else return type_convert_expression (b, make_unsigned_long_int());
  }
  if (is_long_int_type (bt) && is_unsigned_type (at)) {
    if (unsigned_int_fits_long) return type_convert_expression (a, bt);
    else return type_convert_expression (a, make_unsigned_long_int());
  }
  
  if (is_long_int_type (at)) return type_convert_expression (b, at);
  if (is_long_int_type (bt)) return type_convert_expression (a, bt);
  /* both AT and BT are integers */
  if (is_unsigned_type (at)) return type_convert_expression (b, at);
  if (is_unsigned_type (bt)) return type_convert_expression (a, bt);
  
  return int_type;
}

/* binary type checks:
   f (T, a, b)

   T     is the current running type.
   a b   the expressions to check

   if the check yields true, return the type most likely to be used as
   a result.
   */
static Type
both_arithmetic (Type t, expression a, expression b)
{
  Type at = expression_type (a);
  Type bt = expression_type (b);
  if (t) return t;

  if (   !is_arithmetic_type (at)
      || !is_arithmetic_type (bt) ) return t;
  
  return arithmetic_conversion (a, b);
}

static Type
pointer_integral (Type t, expression a, expression b)
{
  Type at = expression_req_type (a);
  Type bt = expression_req_type (b);
  if (t) return t;

  if (   !is_pointer_type (at)
      || !is_integral_type (bt) ) return t;
  
#warning Should integral promotion be applied to pointer add/substract argument?
#if 0
  integral_promotion(b);
#endif
  return at;
}

static Type
both_pointer (Type t, expression a, expression b)
{
  Type at = expression_req_type (a);
  Type bt = expression_req_type (b);
  if (t) return t;
  
  if (is_pointer_type (at)) {
    if ( is_null_pointer (b) ||
         (is_void_pointer_type(bt) && !is_function_type (dereference_type(at))) ||
         ptrs_to_compatible_types (at, bt) ) return int_type;
  }
  if (is_pointer_type (bt)) {
    if ( is_null_pointer (a) ||
         (is_void_pointer_type(at) && !is_function_type (dereference_type(bt))) ||
         ptrs_to_compatible_types (bt, at) ) return int_type;
  }
  return t;      
}

static Type
both_pointer_strict (Type t, expression a, expression b)
{
  Type at = expression_req_type (a);
  Type bt = expression_req_type (b);
  if (t) return t;
  
  if (is_pointer_type (at) &&
      !is_function_type (dereference_type (at)) &&
      ptrs_to_compatible_types (at, bt)) {
    return get_ptrdiff_t (expression__num(a), expression_scope (a));
  }
  if (is_pointer_type (bt) &&
      !is_function_type (dereference_type (bt)) &&
      ptrs_to_compatible_types (bt, at)) {
    return get_ptrdiff_t (expression__num(a), expression_scope (a));
  }
  return t;      
}

/* ----------------------------------------------------------------------------
 *                              STEP 0
 * Clear types in the AST nodes that require it
 * --------------------------------------------------------------------------*/

static void
clear_types_declaration_specifier(declaration_specifier me)
{
  declaration_specifier_type (me) = NULL;
}

/* ----------------------------------------------------------------------------
 *                              STEP 1
 * Assign base types, these are the types that are derived from in the
 * declarators
 * --------------------------------------------------------------------------*/

static Type
filter_std_type (Type a)
{
  assert (Type_tag(a) == SpecType_kind);
  
  if (SpecType_is_long(a)==1) {
    if (is_int_type (a) || is_double_type (a)) return a;
    return NULL;
  }
  if (SpecType_is_long(a)==2) {
    if (is_int_type (a))    return a;
    return NULL;
  }
  if (SpecType_is_long(a)>2) return NULL;
  return a;
}

static Type
combine_types (Type a, Type b)
{
  /* B in { StructType, UnionType, EnumType, IdType } 
     A in { 0, SpecType, StructType, UnionType, EnumType, IdType },
     A!=long_type_spec
  */
  if (b==long_type_spec) b = make_long (NULL);
  if (!a) return b;
  switch (Type_tag(a)) {
  case StructType_kind:
  case UnionType_kind:
  case EnumType_kind: /* only spectypes can be combined with these types */
    if (Type_tag(b) == SpecType_kind) return combine_types (b, a);
    else                              return NULL;
  case IdType_kind:
    if (Type_tag(b) == SpecType_kind) return combine_types (b, a);
    if (a==short_type && b==int_type) return short_type;
    if (b==short_type && a==int_type) return short_type;
    return NULL;
  case SpecType_kind:
    if (Type_tag(b) == SpecType_kind) {
      return combine_specs (a, b);
    } else if (SpecType_base(a)) {
      SpecType_base(a) = combine_types (SpecType_base(a), b);
      if (!SpecType_base(a)) return NULL;
      return a;
    } else {
      SpecType_base(a) = b;
      return filter_std_type (a);
    } 
    break;
  default:
    abort();
  }
}

static Type
make_id_type (TypeId spec, Type u)
{
  declarator d = TypeId_decl (spec);
  Type t = NULL;

  if (d) t = declarator_type (d);
  else undeclared_type_identifier (spec, Ident_name (TypeId_id (spec)));
  
  if (!t || Type_tag(t)!=IdType_kind || !IdType_std(t)) {
    t = Create_IdType (declaration_specifier_src_info (spec), 0, 0,
                       TypeId_id (spec),
                       d);
  }
  t = combine_types (u, t);
  if (!t) {
    invalid_type_specifier (spec, Text_declaration_specifier (spec), Type_name (u,"foo"));
  }
  return t;
}

static Type
make_struct_type (declaration_specifier spec, Type u)
{
  Type t;
  
  if (declaration_specifier_definition (spec)) {
    declaration_specifier def = declaration_specifier_definition (spec);
    if (!declaration_specifier_type (def)) {
      /* forward declaration */
      return specifier_type (def, u);
    }
    t = base_type (declaration_specifier_type (def));
  } else {
    switch (declaration_specifier_tag (spec)) {
    case StructDef_kind:
      t = Create_StructType (declaration_specifier_src_info (spec),
                             0, 0, StructDef_id (spec),
                             StructDef_members (spec), NULL);
      AggrType_defined (t) = TRUE;
      break;
    case StructDecl_kind:
      t = Create_StructType (declaration_specifier_src_info (spec),
                             0, 0, StructDef_id (spec),
                             NULL, NULL);
      break;
    default:
      abort();
    }
  }
  t = combine_types (u, t);
  if (!t) {
    invalid_type_specifier (spec, Text_declaration_specifier (spec), Type_name (u,"foo"));
  }
  return t;
}

static Type
make_union_type (declaration_specifier spec, Type u)
{
  Type t;
  
  if (declaration_specifier_definition (spec)) {
    declaration_specifier def = declaration_specifier_definition (spec);
    if (!declaration_specifier_type (def)) {
      /* forward declaration */
      return specifier_type (def, u);
    }
    t = base_type (declaration_specifier_type (def));
  } else {
    switch (declaration_specifier_tag (spec)) {
    case UnionDef_kind:
      t = Create_UnionType (declaration_specifier_src_info (spec),
                            0, 0, UnionDef_id (spec),
                            UnionDef_members (spec), NULL);
      AggrType_defined (t) = TRUE;
      break;
    case UnionDecl_kind:
      t = Create_UnionType (declaration_specifier_src_info (spec),
                             0, 0, UnionDef_id (spec),
                             NULL, NULL);
      break;
    default:
      abort();
    }
  }
  t = combine_types (u, t);
  if (!t) {
    invalid_type_specifier (spec, Text_declaration_specifier (spec), Type_name (u,"foo"));
  }
  return t;
}

static Type
make_enum_type (Enum spec, Type u)
{
  Type t = NULL;
  
  if (declaration_specifier_definition (spec)) {
    Enum def = declaration_specifier_definition (spec);
    if (declaration_specifier_type (def)) {
      t = base_type (declaration_specifier_type (def));
    } else {
      undefined_enum_type (spec);
    }
  } else {
    t = Create_EnumType (declaration_specifier_src_info (spec),
                         Type_size (int_type), Type_align (int_type),
                         Enum_id (spec),
                         Enum_enums (spec));
  }
  t = combine_types (u, t);
  if (!t) {
    invalid_type_specifier (spec, Text_declaration_specifier (spec), Type_name (u,"foo"));
  }
  return t;
}

static Type
specifier_type (declaration_specifier spec, Type u)
{
  Type t;

  if (declaration_specifier_type (spec)) {
    return declaration_specifier_type (spec);
  }
  switch (declaration_specifier_tag (spec)) {
  case inline_specifier_kind:
  case inline_specifier1_kind:
  case inline_specifier2_kind:
  case StorageClass_kind:
    break; /* not part of the type */
  case Sign_kind:
    if (Sign_si (spec) == UnSigned) t = make_unsigned (u);
    else                            t = make_signed (u);
    break;
  case TypeQual_kind:
    t = add_qualifier (u, TypeQual_qual (spec));
    break;
  case TypeId_kind:
    t = make_id_type (spec, u);
    break;
  case Enum_kind:   t = make_enum_type (spec, u);   break;
  case StructDef_kind: case StructDecl_kind:
    t = make_struct_type (spec, u);
    break;
  case UnionDef_kind: case UnionDecl_kind:
    t = make_union_type (spec, u);
    break;
  }
  declaration_specifier_type (spec) = t;
  return t;
}

/* Side effect: gives type to specifier */
static void
declarator_give_specifier (declarator d, declaration_specifier spec)
{
  Type t = NULL;

  if (d) t = declarator_type (d);
  
  switch (declaration_specifier_tag (spec)) {
  case StorageClass_kind:
    break;
  case inline_specifier_kind:
  case inline_specifier1_kind:
  case inline_specifier2_kind:
    if (d) declarator_is_inline (d) = TRUE;
    break;
  default:
    t  = specifier_type (spec, t);
    if (d) declarator_type (d) = t;
  }
}

/* Side effect: gives type to specifiers */
static void
declarator_give_specifiers (declarator d, declaration_specifiers ds)
{
  List_declaration_specifier specs;
  
  for (specs = declaration_specifiers_specs (ds);
       specs;
       specs = List_declaration_specifier_next (specs)) {
    declaration_specifier spec = List_declaration_specifier_data (specs);
    declarator_give_specifier (d, spec);
  }
}

/** traversal functions **/

static declaration_specifiers
give_base_types_declarator(declarator me, declaration_specifiers ds)
{
  if (!me) return ds;
  declarator_type (me) = NULL;
  if (!ds) return NULL;

  declarator_give_specifiers (me, ds);
  /* We can have a baseless SpecType here, default to int_type */
  if (!declarator_type (me)) {
    declarator_type (me) = int_type;
  } else if (is_spectype (declarator_type (me)) && !SpecType_base (declarator_type (me))) {
    SpecType_base (declarator_type (me)) = int_type;
#if 0
    Type_size(declarator_type (me)) = Type_size(int_type);
    Type_align(declarator_type (me)) = Type_align(int_type);
#else
    sizeof_type (declarator_type (me), NULL);
#endif
  }

  if (!have_longlong && is_long_long_type (declarator_type (me))) {
    no_longlong (me);
  }
  return NULL;
}

static declaration_specifiers
give_base_types_declaration (declaration me, declaration_specifiers ds)
{
  ds = declaration_specs(me);
  if (!declaration_decls (me)) {
    /* No declarators, give types to specifiers */
    declarator_give_specifiers (NULL, ds);
  }
  return ds;
}

static declaration_specifiers
give_base_types_function_header(function_header me, declaration_specifiers ds)
{
  if (function_header_tag (me) != spec_functiondef_kind) return ds;
  return spec_functiondef_specs (me);
}

static declaration_specifiers
give_base_types_ellipsis_declarator(declarator me, declaration_specifiers ds)
{
  NOT_USED(ds);

  declarator_type(me) = Create_EllipsisType (no_srcinfo, 0, 0);
  return NULL;
}

static declaration_specifiers
give_base_types_type_name (type_name me, declaration_specifiers ds)
{
  NOT_USED(ds);
  return type_name_specs(me);
}



/* ----------------------------------------------------------------------------
 *                              STEP 2
 * Compute the derived type of the Id_Decls
 * --------------------------------------------------------------------------*/

static void
type_declarators_pointer_declarator(pointer_declarator me)
{
  Type t = declarator_type (me);
  List_type_qualifier qs;

  assert (t);

  t = pointer_to_type (t);
  for (qs = pointer_declarator_quals(me); qs; qs = List_type_qualifier_next(qs)) {
    t = add_qualifier (t, List_type_qualifier_data(qs));
  }
  declarator_type (pointer_declarator_decl (me)) = t;
}

static void
type_declarators_ParenDecl(ParenDecl me)
{
  Type t = declarator_type (me);
  
  assert (t);
  declarator_type (ParenDecl_decl (me)) = t;
}

static void
type_declarators_ArrayDecl(ArrayDecl me)
{
  Type t = declarator_type (me);

  assert (t);
  
  t = Create_ArrayType (no_srcinfo, 0, 0, ArrayDecl_size(me), t);
  declarator_type (ArrayDecl_pre (me)) = t;
}

static Bool
is_pointer_decl (declarator me)
{
  if (!me) return FALSE;
  switch (declarator_tag(me)) {
    case pointer_declarator_kind: return TRUE;
    case ParenDecl_kind: return is_pointer_decl (ParenDecl_decl(me));
    default: break;
  }
  return FALSE;
}

static void
type_declarators_FuncDecl(FuncDecl me)
{
  storage_class_specifier scs;
  Type t = declarator_type (me);
  
  if (!t) t = declarator_type (me) = int_type;
  scs = declarator_storage_class (me);
  if ((scs == Auto || scs==Register) && !is_pointer_decl(FuncDecl_pre(me))) {
    storage_class_forbidden_here(me, Text_storage_class_specifier (scs));
  }
  
  t = Create_FunctionType (no_srcinfo, SIZEOF_PTR, SIZEOF_PTR, t,
                           parameter_list_pars (FuncDecl_pars (me)),
                           NULL);
  t = type_add_attributes (t, FuncDecl_attrs(me));
  declarator_type (FuncDecl_pre (me)) = t;
}


static Id_Decl
first_composite_Id_Decl(Id_Decl me)
{
  Bind bind;
  Scope scope = declarator_scope (me);
  declarator d;
  
  if (!has_internal_linkage (me) &&
      !has_external_linkage (me)) {
    return NULL;
  }

  bind = RetrieveBind (Id_Decl_id (me), scope,
                       declarator__num(me), DefaultNameSpace,
                       Bind_cfront_declarator_kind);
  if (!bind) return NULL;
  d = Bind_object (bind);
  if (declarator_tag (d) != Id_Decl_kind ||
      declarator_scope (d) != scope) {
    return NULL;
  }
  return d;
}

/* 3.1.2.6: "For an identifier with external or internal linkage
   declared in the same scope as another declaration for that
   identifier, the type of the identifier becomes the composite
   type."
   3.7.1: "A declaration of a parameter as 'array of type' shall 
   be adjusted to 'pointer to type' and a declaration of a parameter 
   of type 'function returning type' shall be adjusted to 
   'function returning pointer to type' as in 3.2.2.1.
*/
static void
type_declarators_Id_Decl(Id_Decl me)
{
/*   declarator d = first_composite_Id_Decl (me); */
/*   if (d) { */
/*     declarator_type(d) = composite_type (declarator_type(d), */
/*                                          declarator_type(me)); */
/*   } */
  Type t = declarator_type(me);
  
  if (file_scope (me)) {
    storage_class_specifier scs = declarator_storage_class (me);
    if (scs==Auto || scs==Register) {
      storage_class_forbidden_here(me, Text_storage_class_specifier (scs));
    } 
  } else if (is_parameter(me)) {
    if (is_array_type (t)) {
      t = pointer_to_type (dereference_type (t));
    } else if (is_function_type (t)) {
      t = pointer_to_type (t);
    }
    declarator_type(me) = t;
  }
  if ( !is_function_type (t) && Id_Decl_id(me) == Create_Ident("main"))
    id_decl_called_main(me); 
}

static void
type_declarators_initDeclarator(initDeclarator me)
{
  Type t = declarator_type(me);
  
  assert (t);
  declarator_type (initDeclarator_decl (me)) = t;
}

static void
type_declarators_DeclStruct(DeclStruct me)
{
  Type t = declarator_type(me);
  
  assert (t);
  if (DeclStruct_bf(me)) {
    t = make_bitfield (t, -1);
    if (unsigned_bitfields && !SpecType_is_signed (t)) {
      t = make_unsigned (t);
    }
  }
  declarator_type (DeclStruct_decl (me)) = t;
}

static void
type_declarators_enumerator(enumerator me)
{
  assert (declarator_type(me));
}

/* ----------------------------------------------------------------------------
 *                              STEP 3
 * Set the type in type holders (parameters, type names, function definitions)
 * --------------------------------------------------------------------------*/

static void
type_holders_Par_Id_Decl (Par_Id_Decl me)
{
  declarator_type (me) = int_type;
  if (Par_Id_Decl_decl (me)) {
    declarator_type (me) = declarator_type (Par_Id_Decl_decl (me));
  }
}

static void
type_holders_initDeclarator(initDeclarator me)
{
  declarator id;
  
  id = get_Id_Decl (initDeclarator_decl (me));
  declarator_type (me) = declarator_type (id);
}

static void
type_holders_type_name(type_name me)
{ 
  storage_class_specifier scs;
  declarator id;
  
  id = get_Id_Decl (type_name_decl (me));
  if (id) {
    scs = declarator_storage_class (id);
    if (scs != NoSCS) {
      storage_class_forbidden_here(me, Text_storage_class_specifier (scs));
    }
    type_name_type (me) = declarator_type (id);
  }
}

static void
type_holders_function_header(function_header me)
{
  declarator id;

  id = get_Id_Decl (function_header_decl (me));
  function_header_type (me) = declarator_type (id);
}

static void
type_old_parameters_Id_Decl (Id_Decl me)
{
  Bind bind = RetrieveBind (Id_Decl_id (me), declarator_scope (me),
                            declarator_loc(me)-1, cfront_DefaultNameSpace,
                            Bind_cfront_declarator_kind);
  Par_Id_Decl param;

  if (!bind) {
    missing_parameter_id (me, Ident_name (Id_Decl_id (me)));
    return;
  }
  param = Bind_object (bind);
  declarator_type (param) = declarator_type (me);
}

static void
type_holders_functionDefinition(functionDefinition me)
{
  Traverse_void_List_declaration (functionDefinition_old_par_decls (me),
                                  &type_old_parameters);
}



/* ----------------------------------------------------------------------------
 *                              STEP 4
 * Finish the types, fills in parameter types, and structure and union members
 * --------------------------------------------------------------------------*/

static void
finish_types_declarator (declarator me)
{
  if (!me) return;
  assert (declarator_type (me));
  declarator_type (me) = decorate_type (declarator_type (me));
}

/* 3.1.2.6: "For an identifier with external or internal linkage
   declared in the same scope as another declaration for that
   identifier, the type of the identifier becomes the composite
   type."
*/
static void
finish_types_Id_Decl (Id_Decl me)
{
  declarator d = first_composite_Id_Decl (me);
  if (d) {
    declarator_type(d) = composite_type (declarator_type(d),
                                         declarator_type(me));
    declarator_type(me) = declarator_type(d);
  }
}

/* ----------------------------------------------------------------------------
 *                              STEP 5.a
 * Bottom Up typing of expressions
 * --------------------------------------------------------------------------*/

static Type
operand_type (expression me)
{ /* 3.2.2.1 */
  Type t = expression_type (me);
  if (Is_lvalue (me)  && is_array_type (t)) {
    t = type_convert_expression (me, pointer_to_type (dereference_type (t)));
  }
  if (is_function_type (t)) {
    t = type_convert_expression (me, pointer_to_type (t));
  }
  return t;
}

static void
BU_typing_Pre_expression (expression me)
{
  if (me) expression_req_type (me) = expression_type (me) = NULL;
}

static void
BU_typing_attribute (attribute me)
{
  if (!user_type_this_attribute ||
      !user_type_this_attribute (me)) {
    return;
  }
  Traverse_void_attr_id (attribute_attr (me), &BU_typing);
}

static void
BU_typing_comma_expression(comma_expression me)
{ /* 3.3.17 */
  inherit_error (me, comma_expression_last (me));
  if (CAST_error (me)) return;
                 
  expression_type (me) = operand_type (comma_expression_last (me));
}

/* ----------------------------------------------------------------------------
 * Convert expression R to type LT
 */
static Type
_assignment_conversion (Type lt, expression r, Bool strict)
{
  Bool ok = FALSE;
  Type t;
  Type rt = operand_type (r);
  
  if (is_arithmetic_type(lt)) {
    ok = is_arithmetic_type(rt);
  }
  else if (is_structured_type (lt)) {
    ok = compatible_types (unqualified_type (lt), unqualified_type (rt));
  }
  else if (is_pointer_type (lt)) {
    /* both operands are pointers to qualified or unqualified
       versions of compatible types, and the type pointed to by the 
       left has all the qualifiers of the type pointed to by the
       right */
    ok = ptrs_to_compatible_types (lt, rt);
    if (is_pointer_type(rt)) chk_qualifiers (dereference_type(lt), dereference_type(rt), r);
    /* one operand is a pointer to an object or incomplete type and
       the other is a pointer to a qualified or unqualified version of
       void, and the type pointed to by the left has all the
       qualifiers of the type pointed to by the right */
    if (is_void_pointer_type(rt)) {
      if (is_function_type(dereference_type(lt))) implicit_cast_to_function (r);
      ok = TRUE;
      chk_qualifiers (lt, rt, r);
    }
    if (is_void_pointer_type(lt) &&
        is_pointer_type(rt)) {
      if (is_function_type(dereference_type(rt))) implicit_cast_from_function (r);
      ok = TRUE;
      chk_qualifiers (lt, rt, r);
    }
    /* the right operand is a null pointer */
    if (is_null_pointer (r)) {
      ok = TRUE;
    } else if (is_integral_type (rt)) {
      implicit_cast_to_pointer (r);
      ok = !strict;
    } else if (!ok && is_pointer_type (rt)) {
      incompatible_pointer_types (r);
      ok = !strict;
    }
  }
  else if (is_internal_type(expanded_base_type (lt))) {
    ok = expanded_base_type(lt)==expanded_base_type(rt);
  }
  
  if (!ok) return NULL;
  t = unqualified_type (lt);
  type_convert_expression (r, t);
  return t;
}

/* ----------------------------------------------------------------------------
 * Perform assignment conversion, does not allow any deviation from
 * the standard
 */
static Bool
strict_assignment_conversion (Type lt, expression r)
{
  return _assignment_conversion (lt, r, TRUE)!=NULL;
}

/* ----------------------------------------------------------------------------
 * Perform assignment conversion, allows deviation from the standard
 * according to the warning settings
 */
static Type
lenient_assignment_conversion (Type lt, expression r)
{
  return _assignment_conversion (lt, r, FALSE);
}


static void 
BU_typing_bin_expression(bin_expression me) 
{
  Bool ok = TRUE;
  Type lt, rt, t = NULL;
  expression l, r;

  l = bin_expression_lhs (me);
  r = bin_expression_rhs (me);

  inherit_error (me, l);
  inherit_error (me, r);
  if (CAST_error (me)) return;
  
  lt = operand_type (l);
  rt = operand_type (r);
  switch (bin_expression_op(me)) {
  case Ass:                           /* 3.3.16.1 */
    t = lenient_assignment_conversion (lt, r);
    break;
  case AssAdd: case AssSub:           /* 3.3.16.2 */
    t = both_arithmetic (t, l, r);
    t = pointer_integral (t, l, r);
    ok = (t!=NULL);
    t = unqualified_type (lt);
    break;
  case AssMul: case AssDiv: case AssMod: /* 3.3.16.2 */
    chk_arithmetic_type (lt, l);
    chk_arithmetic_type (rt, r);
    t = unqualified_type (lt);
    break;
  case AssShl: case AssShr:           /* 3.3.16.2 */
    chk_integral_type (lt, l);
    chk_integral_type (rt, r);
    rt = integral_promotion (r);
    lt = integral_promotion (l);
    t = unqualified_type (lt);
    break;
  case AssAnd: case AssOr: case AssXor: /* 3.3.16.2 */
    chk_integral_type (lt, l);
    chk_integral_type (rt, r);
    t = arithmetic_conversion (l, r);
    t = unqualified_type (t);
    break;
  case CorOp:                         /* 3.3.14 */
  case CandOp:                        /* 3.3.13 */
    chk_scalar_type (lt, l);
    chk_scalar_type (rt, r);
    t = int_type;
    break;
  case OrOp:                          /* 3.3.12 */
  case XorOp:                         /* 3.3.11 */
  case AndOp:                         /* 3.3.10 */
    chk_integral_type (lt, l);
    chk_integral_type (rt, r);
    t = arithmetic_conversion (l, r);
    break;
  case EqOp: case NeOp:               /* 3.3.9 */
    t = both_arithmetic (t, l, r);
    t = both_pointer (t, l, r);
    ok = (t!=NULL);
    t = int_type;
    break;
  case LtOp: case GtOp: case LeOp: case GeOp: /* 3.3.8 */
    t = both_arithmetic (t, l, r);
    t = both_pointer_strict (t, l, r);
    ok = t!=NULL;
    t = int_type;
    break;
  case ShlOp: case ShrOp:             /* 3.3.7 */
    chk_integral_type (lt, l);
    chk_integral_type (rt, r);
    lt = integral_promotion (l);
    rt = integral_promotion (r);
    t = lt;
    break;
  case SubOp:                         /* 3.3.6 */
    t = both_arithmetic (t, l, r);
    t = both_pointer_strict (t, l, r);
    t = pointer_integral (t, l, r);
    break;
  case AddOp:                         /* 3.3.6 */
    t = both_arithmetic (t, l, r);
    t = pointer_integral (t, l, r);
    t = pointer_integral (t, r, l);
    break;
  case MulOp: case DivOp: case ModOp: /* 3.3.5 */
    chk_arithmetic_type (lt, l);
    chk_arithmetic_type (rt, r);
    t = arithmetic_conversion (l, r);
    break;
  case PAddOp: case PSubOp:
    t = pointer_integral (t, l, r);
    break;
  case PAssAdd: case PAssSub:
    t = pointer_integral (t, l, r);
    break;
  case PPSubOp:
    t = both_pointer_strict (t, l, r);
    ok = ( !is_incomplete_type (dereference_type (lt)) &&
           !is_incomplete_type (dereference_type (rt)) );
    break;
  }
  
  inherit_error (me, l);
  inherit_error (me, r);
  if (CAST_error (me)) return;
  
  if (!ok || !t) {
    invalid_type_in_expression (me, Text_expression(me), me, Type_name(lt, ""), me, Type_name(rt, ""));
  }
  expression_type (me) = t;
}

static void 
BU_typing_mon_expression(mon_expression me) 
{
  Type t;
  
  inherit_error (me, mon_expression_arg (me));
  if (CAST_error (me)) return;
                        
  switch (mon_expression_op (me)) {
  case DerefOp:                /* 3.3.3.2 */
    t = operand_type (mon_expression_arg (me));
    if (chk_pointer_type (t, mon_expression_arg (me))) {
      t = dereference_type (t);
    }
    break;
  case AddrOp:                 /* 3.3.3.2 */
    t = expression_type (mon_expression_arg (me));
    chk_non_bitfield (t, me);
    chk_non_register (me);
    t = pointer_to_type (t);
    break;
  case PosOp:  case NegOp:     /* 3.3.3.3 */
    t = integral_promotion (mon_expression_arg (me));
    chk_arithmetic_type (t, me);
    break;
  case InvOp: /* ~ */          /* 3.3.3.3 */
    t = integral_promotion(mon_expression_arg (me));
    chk_integral_type (t, me);
    break;
  case NotOp: /* ! */          /* 3.3.3.3 */
    t = operand_type (mon_expression_arg (me));
    chk_scalar_type (t, me);
    t = int_type;
    break;
  case PreInc: case PreDec:    /* 3.3.3.1 */
  case PostInc: case PostDec:  /* 3.3.2.4 */
    t = operand_type (mon_expression_arg (me));
    chk_scalar_type (t, me);
    break;
  }
  expression_type (me) = t;
}

static Type
CondExpr_pointer_type (expression a, Type at,
                       expression b, Type bt)
{
  /* the result type is a pointer to a type qualified with all the
     type qualifiers of the types pointed-to by both operands */
  
  /* if one operand is a null pointer constant, the result has the
     type of the other operand */
  if (is_null_pointer (b)) return copy_qualifiers (at, bt);

  /* if one operand is a (qualified) pointer to void, the other
     operand is converted to (C9X: an appropriately qualified version
     of) type pointer to void, and the result has that type */
  if (is_void_pointer_type(bt) &&
      !is_function_type (dereference_type (at))) {
    at = copy_qualifiers (bt,at);
    type_convert_expression (a, at);
    return at;
  }

  /* if both operands are pointers to (differently qualified versions
     of) compatible types, the result has the composite type. */
  if (ptrs_to_compatible_types (at, bt)) {
    return composite_type (at, bt);
  }
  return NULL;
}

static void 
BU_typing_CondExpr(CondExpr me) 
{  /* 3.3.15 */
  Type t = NULL;
  expression cond, thn, els;
  Type cond_type, thn_type, els_type;
  
  cond = CondExpr_cond (me);
  thn  = CondExpr_thn (me);
  els  = CondExpr_els (me);

  inherit_error (me, thn);
  inherit_error (me, els);
  inherit_error (me, cond);
  if (CAST_error (me))    return;
  
  cond_type = operand_type (cond);
  thn_type = operand_type (thn);
  els_type = operand_type (els);
  
  chk_scalar_type (cond_type, cond);

  t = both_arithmetic (t, thn, els);
  
  if (!t && is_void_type (thn_type) && is_void_type(els_type)) {
    t = thn_type;
  }
  
  if (!t) t = CondExpr_pointer_type (thn, thn_type, els, els_type);
  if (!t) t = CondExpr_pointer_type (els, els_type, thn, thn_type);

  if (!t && is_structured_type (thn_type)) {
    if (compatible_types (thn_type, els_type)) t = thn_type;
  }
  if (!t) incompatible_alternatives (me);
  else expression_type(me) = t;
}

static void 
BU_typing_CastExpr(CastExpr me) 
{ /* 3.3.4 */
  Type t = type_name_type (CastExpr_casts (me));

  inherit_error (me, CastExpr_expr (me));
  if (CAST_error (me))    return;
  
  if (!is_void_type(t)) {
    if (!is_scalar_type (t)) non_scalar_cast (CastExpr_casts (me));
    chk_scalar_type (operand_type (CastExpr_expr (me)), CastExpr_expr (me));
  }
  expression_type (me) = t;
  type_convert_expression (CastExpr_expr (me), t);
}

static void 
BU_typing_SizeofExpr(SizeofExpr me) 
{ /* 3.3.3.4 */
  Type t = expression_type (SizeofExpr_expr (me));

  inherit_error (me, SizeofExpr_expr (me));
  if (CAST_error (me))    return;
  
  chk_non_function  (t, SizeofExpr_expr (me));
  chk_complete_type (t, SizeofExpr_expr (me));
  chk_non_bitfield  (t, SizeofExpr_expr (me));
  expression_type (me) = get_size_t (expression__num(me), expression_scope (me));
}

static void 
BU_typing_SizeofType(SizeofType me) 
{ /* 3.3.3.4 */
  Type t = type_name_type (SizeofType_tname (me));
  
  chk_non_function  (t, me);
  chk_complete_type (t, me);
  chk_non_bitfield  (t, me);
  expression_type (me) = get_size_t (expression__num(me), expression_scope (me));
}

static void 
BU_typing_IndexExpr(IndexExpr me) 
{ /* 3.3.2.1 */
  expression array = IndexExpr_array (me);
  expression index = IndexExpr_index (me);
  Type arrayt, indext;

  inherit_error (me, array);
  inherit_error (me, index);
  if (CAST_error (me))    return;
  
  /* One of the expressions shall have type "pointer to type" */
  indext = operand_type (index);
  arrayt = operand_type (array);
  if (is_pointer_type (indext)) {
    Type t = arrayt;
    arrayt = indext;
    indext = t;
  } else {
    if (!chk_pointer_type (arrayt, array)) {
      inherit_error (me, array);
      return;
    }
  }
  if (is_incomplete_type (dereference_type (arrayt))) {
    incomplete_type_forbidden (me, Text_expression (array));
  }
  if (is_function_type (dereference_type (arrayt))) {
    function_type_forbidden (me, Text_expression (array));
  }
  chk_integral_type (indext, index);
  expression_type (me) = dereference_type (arrayt);
}

static void
argument_conversion (expression arg, Type t, int n)
{
  if (!t || is_ellipsis_type (t)) {
    if (!CAST_error (arg)) {
      default_argument_promotion (arg);
    }
    return;
  }
  if (!CAST_error (arg) &&
      !strict_assignment_conversion (pointer_promote (t), arg)) {
    incompatible_parameter (arg, n,
                            Type_name (operand_type (arg),"bar"),
                            Type_name (expanded_base_type (t),"foo"));
  }
}

static void 
BU_typing_CallExpr(CallExpr me) 
{ /* 3.3.2.2 */
  int n;
  Bool implicit;
  expression func = CallExpr_func (me);
  expression arg;
  Type argt;
  List_expression es;
  List_Type ts;
  Type f = expression_type (func);
  Type r;
  Bool old_style;

  implicit = (f==NULL && expression_tag (func) == IdExpr_kind);
  if (implicit) {
    withdraw_error (func);
    expression_type (func) = implicit_function_type;
    undeclared_function(me, Ident_name(IdExpr_id_id(func)));
  } else {
    inherit_error (me, func);
    if (CAST_error (me))   return;
  }
  f = operand_type (func);
  
  if (!chk_ptr_to_function_type (f, func)) return;
  f = dereference_type (f);
  r = function_result_type (f);
  chk_non_array_type (r, me); 
  expression_type (me) = r;
 
  old_style = function_arg_types (f) == NULL;
  for (es = CallExpr_args (me), ts = function_arg_types (f), n = 1;
       es;
       es = List_expression_next (es), n++) {
    arg = List_expression_data (es);
    if (ts) argt = List_Type_data (ts);
    else    argt = NULL;
    
    argument_conversion (arg, argt, n);
    if (!old_style) {
      if (!ts) break;
      if (argt && !is_ellipsis_type(argt)) {
        ts = List_Type_next (ts);
      }
    }
  }
  if (es) {
    too_many_parameters (arg);
  } else if (ts) {
    argt = List_Type_data (ts);
    if (!is_ellipsis_type (argt) &&
        !is_void_type (argt)) {
      missing_parameters (func);
    }
  }
}

static void 
BU_typing_MemberExpr(MemberExpr me) 
{ /* 3.3.2.3 */
  expression aggr = MemberExpr_aggr (me);
  Type r, t;
  SimpleDecl mem;

  inherit_error (me, aggr);
  if (CAST_error (me))   return;
  
  r = operand_type (aggr);
  if (!chk_struct_type (r, aggr)) {
    CAST_copy_error (me, aggr);
    return;
  }
  
  mem = struct_member (r, MemberExpr_member (me));
  if (!mem) {
    missing_member (me, Ident_name (MemberExpr_member (me)));
  } else {
    t = unqualified_type (SimpleDecl_type (mem));
    expression_type (me) = copy_qualifiers (t, r);
  }
}

static void 
BU_typing_DerefMemberExpr(DerefMemberExpr me) 
{ /* 3.3.2.3 */
  expression aggr = DerefMemberExpr_aggr (me);
  Type r, t;
  SimpleDecl mem;

  inherit_error (me, DerefMemberExpr_aggr (me));
  if (CAST_error (me))   return;
  
  r = operand_type (aggr);  
  if (!chk_pointer_type (r, aggr)) {
    CAST_copy_error (me, aggr);
    return;
  }
  r = dereference_type (r);
  if (!chk_struct_type (r, aggr)) {
    CAST_copy_error (me, aggr);
    return;
  }
  mem = struct_member (r, DerefMemberExpr_member (me));
  if (!mem) {
    missing_member (me, Ident_name (MemberExpr_member (me)));
  } else {
    t = unqualified_type (SimpleDecl_type (mem));
    expression_type (me) = copy_qualifiers (t, r);
  }
}

static void 
BU_typing_IdExpr(IdExpr me) 
{ /* 3.3.1 */
  if (!IdExpr_decl (me)) {
    undeclared_identifier (me, Text_expression (me));
    return;
  }
  expression_type(me) = declarator_type (IdExpr_decl (me));
}

static void 
BU_typing_ParExpr(ParExpr me) 
{ /* 3.3.1 */
  inherit_error (me, ParExpr_expr (me));
  if (CAST_error (me))   return;
  /* Note: we cannot take the operand_type of the element, since that
     will convert arrays to pointers, which will screw up sizeof(expr) */
  expression_type (me) = expression_type (ParExpr_expr (me));
}

static void 
BU_typing_NumExpr(NumExpr me) 
{ /* 3.1.3.2 */
  AP_Integer val = NumExpr_val(me);
  Type t = int_type;
  Bool done;
  char *s = NumExpr_i (me);
  int l = strlen(s)-1;
  int us=0, ls=0, lls=0;
  Bool is_decimal;

  assert (val);
  /* parse the unsigned and long suffixes */
  for (done=FALSE; l && !done; l--) {
    switch (s[l]) {
    case 'u': case 'U':
      us++;
      break;
    case 'l': case 'L':
      if (s[l+1]==s[l]) lls++;
      else ls++;
      break;
    default:
      done = TRUE;
    }
  }
  if (us>1 || ls>1 || lls>1) {
    invalid_integer_constant (me);
    return;
  }
  if (lls && !have_longlong) {
    no_longlong (me);
    return;
  }

  /* Parse the radix prefixes: */
  /* All numbers that start in 0x or 0X are hex, those starting in 0 are octal. */
  is_decimal = s[0] != '0';

  if (lls)     t = make_long_long_int();
  else if (ls) t = make_long_int();
  if (us)      t = make_unsigned (t);

  if (is_decimal) {
    if (!constant_fits (val, t)) t = make_long_int();
    if (have_longlong) {
      if (!constant_fits (val, t)) t = make_long_long_int();
    } else {
      if (!constant_fits (val, t)) t = make_unsigned (t); /* C89 rule. */;
    }
  } else {
    if (!constant_fits (val, t)) t = make_unsigned (t);
    if (!constant_fits (val, t)) t = make_long_int ();
    if (!constant_fits (val, t)) t = make_unsigned (t);
    if (!constant_fits (val, t)) t = make_long_long_int ();
    if (!constant_fits (val, t)) t = make_unsigned (t);
  }
  if (!constant_fits (val, t)) constant_too_large (me);

  expression_type (me) = t;
}

static void 
BU_typing_CharExpr(CharExpr me) 
{ /* 3.1.3.4 */
  expression_type (me) = int_type;
}

static void 
BU_typing_WideCharExpr(CharExpr me) 
{ /* 3.1.3.4 */
  expression_type (me) = get_wchar_t (expression__num (me),
                                      expression_scope (me));
}

static void 
BU_typing_FloatExpr(FloatExpr me) 
{ /* 3.1.3.1 */
  Type t;
  char *s = FloatExpr_f (me);
  int l = strlen(s)-1;

  /* parse the unsigned and long suffixes */
  switch (s[l]) {
  case 'f': case 'F': t = float_type; break;
  case 'l': case 'L': t = make_long_double(); break;
  default:            t = double_type; break;
  }
  expression_type (me) = t;
}

static void 
BU_typing_StringExpr(StringExpr me) 
{ /*3.1.4 */
  /* Pre: ast_translate_strings has been done */
  Type t = char_type;
  expression size;
  
  if (StringExpr_wide (me)) {
    t = get_wchar_t (expression__num (me), expression_scope (me));
  }
  size = Create_IntExpr(expression_src_info(me), StringExpr_size (me));
  expression_type (me) = Create_ArrayType (no_srcinfo, 0, 0,
                                           size, t);
}

static void 
BU_typing_TypeExpr(TypeExpr me) 
{ /* GNU extension */
  expression_type (me) = type_name_type (TypeExpr_typename(me));
}

static void 
BU_typing_StatExpr(StatExpr me) 
{ /* GNU extension */
  /* From the info file:
   The last thing in the compound statement should be an expression
followed by a semicolon; the value of this subexpression serves as the
value of the entire construct.  (If you use some other kind of statement
last within the braces, the construct has type `void', and thus
effectively no value.)
   */
  statement last;
  Type t;

  last = List_last ((Front_List) compound_statement_body (StatExpr_stat(me)));
  if (statement_tag(last) != ExprStat_kind) t = void_type;
  else {
    inherit_error (me, ExprStat_expr (last));
    if (CAST_error (me))   return;
    t = operand_type (ExprStat_expr (last));
  }
  expression_type (me) = t;
}

static void 
BU_typing_CompoundLit(CompoundLit me) 
{ /* GNU extension, and C99 */
  expression_type (me) = type_name_type (CompoundLit_casts (me));
}


static void
BU_typing_IfStat (IfStat me)
{ /* 3.6.4.1 */
  expression c = IfStat_cond (me);

  inherit_error (me, c);
  if (CAST_error (me))   return;
  chk_scalar_type (operand_type (c), c);
}

static void
BU_typing_SwitchStat (SwitchStat me)
{ /* 3.6.4.2 */
  expression c = SwitchStat_sw (me);

  inherit_error (me, c);
  if (CAST_error (me))   return;
  chk_integral_type (operand_type (c), c);
}

static void
BU_typing_WhileStat (WhileStat me)
{ /* 3.6.5.1 */
  expression c = WhileStat_cond (me);

  inherit_error (me, c);
  if (CAST_error (me))   return;
  chk_scalar_type (operand_type (c), c);
}

static void
BU_typing_DoStat (DoStat me)
{ /* 3.6.5.2 */
  expression c = DoStat_cond (me);

  inherit_error (me, c);
  if (CAST_error (me))   return;
  chk_scalar_type (operand_type (c), c);
}


static void
BU_typing_ForStat (ForStat me)
{ /* 3.6.5.3 */
  expression c = ForStat_cond (me);

  if (!c) return;
  inherit_error (me, c);
  if (CAST_error (me))   return;
  chk_scalar_type (operand_type (c), c);
}

static void
BU_typing_ReturnStat (ReturnStat me)
{ /* 3.6.6.4 */
  function_header head = functionDefinition_head (statement_cur_func (me));
  Type func = function_header_type (head);
  Type result;

  assert (func);
  assert (is_function_type (func));
  result = function_result_type (func);

  if (ReturnStat_expr (me)) {
    inherit_error (me, ReturnStat_expr (me));
    if (CAST_error (me))   return;
    
    if (is_void_type (result)) {
      return_in_void_function (ReturnStat_expr (me));
    }
    type_convert_expression (ReturnStat_expr (me), result);
  } else {
    if (!is_void_type (result)) {
      missing_return_value (me);
    }
  }
}

/* ----------------------------------------------------------------------------
 * In declarators, type expressions first
 * --------------------------------------------------------------------------*/

static void
BU_typing_ArrayDecl(ArrayDecl me)
{
  Traverse_void_expression (ArrayDecl_size(me),  &BU_typing);
#if 0
  Traverse_void_gnu_attrs  (ArrayDecl_attrs(me), &BU_typing);
#endif
  Traverse_void_declarator (ArrayDecl_pre(me),   &BU_typing);
}

static void
BU_typing_Pre_DeclStruct(DeclStruct me)
{
  Traverse_void_expression (DeclStruct_bf(me),    &BU_typing);
  Traverse_void_declarator (DeclStruct_decl(me),  &BU_typing);
}

/* ----------------------------------------------------------------------------
 *                              STEP 5.b
 * Compute the value of enumerators
 * --------------------------------------------------------------------------*/

static void
BU_typing_enumerator(enumerator me)
{
  mpz_t v;
  
  mpz_init (v);
  if (enumerator_c (me)) {
    enumerator_v (me) = EvalIntExpr (enumerator_c (me));
  } else {
    enumerator pred = enumerator_pred (me);
    
    assert (!pred || enumerator_v (pred));
    if (pred) mpz_add_ui (v, *enumerator_v (pred), 1);
    enumerator_v (me) = AP_Int (v);
  }
}

/* ----------------------------------------------------------------------------
 *                              STEP 5.c
 * Compute the size of bitfields
 * --------------------------------------------------------------------------*/

static void
BU_typing_Post_DeclStruct (DeclStruct me)
{
  Bool ok;
  int bits;
  Type t;
  AP_Integer v;
  
  if (!DeclStruct_bf(me)) return;
  t = declarator_type (DeclStruct_decl (me));
  assert (is_bitfield_type (t));
  if (!is_integer_type (t)) {
    int e = 0;
    if (expanded_base_type (t)!=int_type) {
      e = bit_field_not_int (me);
    } 
    if (!e) invalid_bit_field_type (me);
    return;
  }
  v = EvalIntExpr (DeclStruct_bf (me));
  if (!v) {
    integral_expression_required (DeclStruct_bf (me));
    return;
  }
  SpecType_bit_width (t) = mpz_get_si (*v);
  if (SpecType_bit_width (t)<0) negative_bit_width (me);
  bits = (int)bits_of_type (t, &ok);
  assert (ok);
  if (bits < SpecType_bit_width (t)) bit_field_too_large (me);
}

/* ----------------------------------------------------------------------------
 *                              STEP 5.d
 * Compute the types of initializers
 * --------------------------------------------------------------------------*/

static void
set_next_offset(Type t, List_expression es)
{
  Bool ok = TRUE;
  expression e = List_expression_data (es);
  List_expression next = List_expression_next (es);
  if (next && List_expression_data (next)) {
    expression n = List_expression_data (next);    
    expression_offset (n) = expression_offset (e) + sizeof_type (t, &ok);
    if ( expression_tag(n) == CompoundInit_kind )
      expression_offset ( HEAD(CompoundInit_inits(n)) ) = expression_offset(n);
    if (!ok) initializing_incomplete_type (e);
  }
}

static List_expression
scalar_initializer (Type t, List_expression es)
{ /* Pre: T is a scalar type */
  List_expression next = List_expression_next (es);
  expression e = List_expression_data (es);
  
  /* The initializer for a scalar shall be a single expression,
     optionally enclosed in braces */
  if (!e) return next;
  if (expression_tag (e) == CompoundInit_kind) {
    List_expression inits = CompoundInit_inits (e);
    expression init = List_expression_data (inits);
       
    if (expression_tag (init) == CompoundInit_kind ) {
      scalar_type_required (init, Text_expression (init));
      return List_expression_next (es);
    }
    if (List_expression_next (inits)) {
      excess_elements (init);
      List_expression_next (inits) = NULL;          
    }         
    expression_type (e) = t;
    e = init;    
  }
  type_convert_expression (e, t);
  return next;
}

static List_expression
array_initializer (Type t, List_expression es)
{
  Bool ok = TRUE;
  List_expression next = NULL;
  expression e;
  Type u = expanded_base_type (t);
  Type elem = ArrayType_element (u);
  size_t i;  
  
  e = List_expression_data (es);
  if (e) {
    if (expression_tag (e) == CompoundInit_kind) {
      next = List_expression_next (es);
      if (next && List_expression_data (next)) {
        expression n = List_expression_data (next);
        expression_offset (n) = expression_offset(e) + sizeof_type(t, &ok);
        assert (ok);
      }
      es = CompoundInit_inits (e);
      expression_type (e) = t;
      type_convert_expression (e, t);
      e = List_expression_data (es);    
    }
    if (expression_tag (e) == StringExpr_kind &&  ptrs_to_compatible_types (t, expression_type (e))) {
      type_convert_expression (e, t);
      if (ArrayType_a_size (u)) {
        if (ArrayType_size (u)+1 < StringExpr_size (e)) {
          string_too_large (e);
        }
      } else {
        ArrayType__size (u) = StringExpr_size (e);
      }      
      return List_expression_next (es);
    }
  }
  
  if (ArrayType_a_size (u)) {
    size_t size = ArrayType_size (u);    
    for (i=0; i<size && es; i++) {
      es = type_initializer (elem, es);
    }
  } else {
    for (i=0; es; i++) {
      es = type_initializer (elem, es);
    }
    ArrayType__size (u) = i;
  } 
  if (next) { 
    if (es) excess_elements(HEAD(es));
    return next;
  }  
  return es;
}

static List_expression
struct_initializer (Type t, List_expression es)
{
  Bool ok = TRUE;
  List_SimpleDecl mems;
  List_expression next = NULL;
  expression e;
  Type u = expanded_base_type (t);
  
  e = List_expression_data (es);
  if (e) {
    if (expression_tag (e) == CompoundInit_kind) {
      next = List_expression_next (es);   
      if (next && List_expression_data (next)) {
        expression n = List_expression_data (next);
        expression_offset (n) = expression_offset(e) + sizeof_type(t, &ok);
        assert (ok);
      }   
      es = CompoundInit_inits (e);     
      expression_type (e) = t;
      type_convert_expression (e, t);
      e = List_expression_data (es);     
    }
    if (expression_type (e) &&
        strict_assignment_conversion (t, e)) {      
      return List_expression_next (es);
    }
  }
  for (mems = AggrType_mems (u);
       mems && es;
       mems = List_SimpleDecl_next (mems)) {
    SimpleDecl mem = List_SimpleDecl_data (mems);
    es = type_initializer (SimpleDecl_type (mem), es);
  } 
  if (next) {    
    if (es) excess_elements(es);
    return next;
  } 
  return es;
}

static List_expression
union_initializer (Type t, List_expression es)
{
  Bool ok = TRUE;
  SimpleDecl mem;
  List_expression next = NULL;
  expression e;
  Type u = expanded_base_type (t);
  
  assert (u);
  e = List_expression_data (es);
  if (e) {
    if (expression_tag (e) == CompoundInit_kind) {
      next = List_expression_next (es);     
      es = CompoundInit_inits (e);     
      expression_type (e) = t;
      type_convert_expression (e, t);
      e = List_expression_data (es);
    }
    if (expression_type (e) &&
        strict_assignment_conversion (t, e)) {     
      return List_expression_next (es);
    }
  }
  mem = AggrType_member1 (u);
  es = type_initializer (SimpleDecl_type (mem), es);  
  if (next && List_expression_data (next)) {
    expression n = List_expression_data (next);
    expression_offset (n) += sizeof_type(t, &ok);
    if (!ok) initializing_incomplete_type (e);
    return next;
  } 
  return es;
}

static List_expression
type_initializer (Type t, List_expression es)
{ /* 3.5.7 */
  Type u;
  
  if (!es) return NULL;
  u = expanded_base_type (t);
  set_next_offset (t, es);
  switch (Type_tag (u)) {
  case IdType_kind: case PointerType_kind: case EnumType_kind:
    return scalar_initializer (t, es);
  case ArrayType_kind:  return array_initializer (t, es);
  case StructType_kind: return struct_initializer (t, es);
  case UnionType_kind:  return union_initializer (t, es);
    
  case FunctionType_kind: case EllipsisType_kind: case SpecType_kind:
    abort();
  }
  return NULL;
}

static void
BU_typing_initDeclarator (initDeclarator me)
{ /* 3.5.7 */
  type_holders_initDeclarator (me);
  Type t = declarator_type (me);
  expression init = initDeclarator_init (me);
  List_expression es = Create_List_expression (init, NULL);
  Type t2 = expression_type (init);

  if (!initDeclarator_init (me)) return;
  switch(Type_tag(expanded_base_type(t))) {
    case ArrayType_kind:
      if ( expression_tag(initDeclarator_init(me)) == StringExpr_kind ) break;           
    case StructType_kind:
    case UnionType_kind:
      if ( expression_tag(initDeclarator_init(me)) == CompoundInit_kind ) break;
      if (Type_tag(expanded_base_type(t)) == Type_tag(expanded_base_type(t2))) break;
      invalid_initializer(me);
      return;      
    default:
      break;
  }  
  expression_offset (init) = 0;
  type_initializer (t, es);
} 

/* ----------------------------------------------------------------------------
 *                              STEP 5.e
 * Set the required type to the supplied type if not set
 * --------------------------------------------------------------------------*/
static void
BU_typing_Post_expression (expression me)
{
  if (me && !expression_req_type (me)) {
    expression_req_type (me) = expression_type (me);
  }
}

/* ----------------------------------------------------------------------------
 *                              STEP 6
 * Check whether all expressions have a type
 * --------------------------------------------------------------------------*/

static void
check_typing_expression (expression me)
{
  assert (!me || expression_type (me));
}

/* ----------------------------------------------------------------------------
 * Fill traverse tables
 */
static void
init_traversals(void)
{
  static Bool done = FALSE;
  if (done) return;
  done = TRUE;

  /* 0. Clear old types */
  clear_types.action_declaration_specifier [PRE_ACTION] = clear_types_declaration_specifier;
  
  /* 1. Assign base types to the top declarators,
   * eg: int, const char, also struct foo { int bar; }, but not derivations
   * like int *, int [], int ()
   */
  give_base_types.traversal                             = Traverse_Down;
  give_base_types.action_declaration[PRE_ACTION]        = (void*)give_base_types_declaration;
  give_base_types.action_function_header[PRE_ACTION]    = (void*)give_base_types_function_header;
  give_base_types.action_type_name[PRE_ACTION]          = (void*)give_base_types_type_name;
  give_base_types.action_declarator[PRE_ACTION]         = (void*)give_base_types_declarator;
  give_base_types.action_ellipsis_declarator[PRE_ACTION] = (void*)give_base_types_ellipsis_declarator;

  /* 2. Compute the derived types of the Id_Decls */
  type_declarators.action_pointer_declarator [PRE_ACTION] = type_declarators_pointer_declarator;
  type_declarators.action_ParenDecl [PRE_ACTION]        = type_declarators_ParenDecl;
  type_declarators.action_ArrayDecl [PRE_ACTION]        = type_declarators_ArrayDecl;
  type_declarators.action_FuncDecl  [PRE_ACTION]        = type_declarators_FuncDecl;
  type_declarators.action_Id_Decl   [PRE_ACTION]        = type_declarators_Id_Decl;
  type_declarators.action_DeclStruct [PRE_ACTION]       = type_declarators_DeclStruct;
  type_declarators.action_initDeclarator [PRE_ACTION]   = type_declarators_initDeclarator;
  type_declarators.action_enumerator [PRE_ACTION]       = type_declarators_enumerator;
  
  /* 3. give types to type holders */
  type_old_parameters.skip_children_parameter_list = TRUE;
  type_old_parameters.action_Id_Decl [PRE_ACTION]       = type_old_parameters_Id_Decl;
  
  type_holders.action_Par_Id_Decl [POST_ACTION]         = type_holders_Par_Id_Decl;
  type_holders.action_initDeclarator [POST_ACTION]      = type_holders_initDeclarator;
  type_holders.action_type_name [POST_ACTION]           = type_holders_type_name;
  type_holders.action_function_header [POST_ACTION]     = type_holders_function_header;
  type_holders.action_functionDefinition [PRE_ACTION]   = type_holders_functionDefinition;
  
  /* 4. Fill in the function type parameters and structure and union members */
  finish_types.action_Id_Decl [PRE_ACTION]              = finish_types_Id_Decl;
  finish_types.action_declarator [POST_ACTION]          = finish_types_declarator;

  /* 5. Compute the supplied type of expressions.  This is a bottom up
     typing.  Also computes array sizes
  */
  BU_typing.skip_children_attribute               = TRUE; 
  BU_typing.action_attribute [PRE_ACTION]         = BU_typing_attribute;
  BU_typing.action_expression [PRE_ACTION]        = BU_typing_Pre_expression;
  BU_typing.action_comma_expression [POST_ACTION] = BU_typing_comma_expression;
  BU_typing.action_bin_expression [POST_ACTION]   = BU_typing_bin_expression;
  BU_typing.action_mon_expression [POST_ACTION]   = BU_typing_mon_expression;
  BU_typing.action_CondExpr [POST_ACTION]         = BU_typing_CondExpr;
  BU_typing.action_CastExpr [POST_ACTION]         = BU_typing_CastExpr;
  BU_typing.action_SizeofExpr [POST_ACTION]       = BU_typing_SizeofExpr;
  BU_typing.action_SizeofType [POST_ACTION]       = BU_typing_SizeofType;
  BU_typing.action_IndexExpr [POST_ACTION]        = BU_typing_IndexExpr;
  BU_typing.action_CallExpr [POST_ACTION]         = BU_typing_CallExpr;
  BU_typing.action_MemberExpr [POST_ACTION]       = BU_typing_MemberExpr;
  BU_typing.action_DerefMemberExpr [POST_ACTION]  = BU_typing_DerefMemberExpr;
  BU_typing.action_IdExpr [POST_ACTION]           = BU_typing_IdExpr;
  BU_typing.action_ParExpr [POST_ACTION]          = BU_typing_ParExpr;
  BU_typing.action_NumExpr [POST_ACTION]          = BU_typing_NumExpr;
  BU_typing.action_CharExpr [POST_ACTION]         = BU_typing_CharExpr;
  BU_typing.action_WideCharExpr [POST_ACTION]     = BU_typing_WideCharExpr;
  BU_typing.action_FloatExpr [POST_ACTION]        = BU_typing_FloatExpr;
  BU_typing.action_StringExpr [POST_ACTION]       = BU_typing_StringExpr;
  BU_typing.action_TypeExpr [POST_ACTION]         = BU_typing_TypeExpr;
  BU_typing.action_StatExpr [POST_ACTION]         = BU_typing_StatExpr;
  BU_typing.action_CompoundLit [POST_ACTION]      = BU_typing_CompoundLit;  
  BU_typing.action_expression [POST_ACTION]       = BU_typing_Post_expression;

  BU_typing.skip_children_ArrayDecl               = TRUE;
  BU_typing.action_ArrayDecl [PRE_ACTION]         = BU_typing_ArrayDecl;
  BU_typing.skip_children_DeclStruct              = TRUE;
  BU_typing.action_DeclStruct [PRE_ACTION]        = BU_typing_Pre_DeclStruct;
  
  BU_typing.action_enumerator [POST_ACTION]       = BU_typing_enumerator;
  BU_typing.action_DeclStruct [POST_ACTION]       = BU_typing_Post_DeclStruct;
  BU_typing.action_initDeclarator [POST_ACTION]   = BU_typing_initDeclarator;
  
  BU_typing.action_IfStat [POST_ACTION]           = BU_typing_IfStat;
  BU_typing.action_SwitchStat [POST_ACTION]       = BU_typing_SwitchStat;
  BU_typing.action_WhileStat [POST_ACTION]        = BU_typing_WhileStat;
  BU_typing.action_DoStat [POST_ACTION]           = BU_typing_DoStat;
  BU_typing.action_ForStat [POST_ACTION]          = BU_typing_ForStat;
  BU_typing.action_ReturnStat [POST_ACTION]       = BU_typing_ReturnStat;
   /* not used: LabeledInit, CompoundInit */
   
  /* 6. ensure all empty req_types are set to the type */ 
  check_typing.action_expression [PRE_ACTION]     = check_typing_expression;
  check_typing.skip_children_initDeclarator       = TRUE;
  check_typing.skip_children_attr_pars = TRUE; /* Don't type attributes */
}

Bool
_ast_give_types (void *node, void *trav(), void trav_void())
{
  init_traversals();

  egg_exit_on_errors();
  trav_void (node, &clear_types);
  trav      (node, &give_base_types, NULL);
  trav_void (node, &type_declarators);
  trav_void (node, &type_holders);
  trav_void (node, &finish_types);
  trav_void (node, &BU_typing);  

  if (egg_has_errors ()) return FALSE; /* Check expressions for types only if we haven't seen any errors yet. */
  trav_void (node, &check_typing);

  return TRUE;
}


Bool
cfront_give_types(cfront root)
{
  return ast_give_types (cfront, root);
}
